﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200716
    {
        //不同出口可行方案
        private static Dictionary<char, int[]> keyValues = new Dictionary<char, int[]>();
        //出口
        private static Dictionary<int, char[]> _out = new Dictionary<int, char[]>();
        //位移矩阵索引
        private static Dictionary<char, int> _mvIndex = new Dictionary<char, int>();
        
        private int[,] _status;
        static AlgorithmCenter200716()
        {
            _out.Add(1, new char[] { 'l', 'r' });
            _out.Add(2, new char[] { 'u', 'b' });
            _out.Add(3, new char[] { 'l', 'b' });
            _out.Add(4, new char[] { 'r', 'b' });
            _out.Add(5, new char[] { 'l', 'u' });
            _out.Add(6, new char[] { 'r', 'u' });

            int[] al = new int[] { 1, 4, 6 };
            int[] ar = new int[] { 1, 3, 5 };
            int[] au = new int[] { 2, 3, 4 };
            int[] ab = new int[] { 2, 5, 6 };            
            keyValues.Add('l', al);
            keyValues.Add('r', ar);
            keyValues.Add('u', au);
            keyValues.Add('b', ab);

            _mvIndex.Add('l',3);
            _mvIndex.Add('r',1);
            _mvIndex.Add('u',0);
            _mvIndex.Add('b',2);

        }

        /// <summary>
        /// https://leetcode-cn.com/problems/check-if-there-is-a-valid-path-in-a-grid/
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public bool HasValidPath(int[][] grid)
        {
            _status = new int[grid.GetLength(0),grid[0].Length];
            return Dfs(0,0,grid);
        }

        public bool Dfs(int x,int y,int[][] temp)
        {
            //将当前的单元格设置为走过
            _status[x,y] = 1;
            //如果发现已经到达目的单元格，则直接返回
            if (x == temp.GetLength(0) - 1 && y == temp[x].Length - 1)
                return true;

            //上下左右位移矩阵
            int[] xmv = {-1, 0, 1, 0 };
            int[] ymv = { 0, 1, 0, -1};
            
            //根据当前单元格类型获取出口集合
            _out.TryGetValue(temp[x][y],out char[] outTemp);
            //遍历所有出口寻找可移动的下一个单元格
            foreach (char c in outTemp)
            {
                //获取从当前出口移动到下一单元格的位移
                _mvIndex.TryGetValue(c, out int index);
                //计算下一单元格坐标
                int dx = x + xmv[index];
                int dy = y + ymv[index];

                //判断坐标是否满足条件
                if (dx >= 0 && dx < temp.GetLength(0) && dy >= 0 && dy < temp[dx].Length && _status[dx, dy] != 1)
                {
                    //获取从当前单元格可以出去的下一单元格类型
                    keyValues.TryGetValue(c, out int[] res);
                    //检查下一单元格的类型是否在满足的单元格类型集合内
                    foreach (int n in res)
                    {
                        if (temp[dx][dy] == n)
                        {
                            //如果在的话，则继续深度行走
                            if (Dfs(dx, dy, temp))
                                return true;
                        }
                    }

                }
            }
            
            return false;
        }

    }
}
